package com.hy.treeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class TreeNodeReserve {


    /**
     * 226.翻转二叉树
     * 力扣题目链接
     *
     * 翻转一棵二叉树。
     *
     * 思路
     * 我们之前介绍的都是各种方式遍历二叉树，这次要翻转了，感觉还是有点懵逼。
     * 这得怎么翻转呢？
     * 如果要从整个树来看，翻转还真的挺复杂，整个树以中间分割线进行翻转，如图：
     *
     * 可以发现想要翻转它，其实就把每一个节点的左右孩子交换一下就可以了。
     *
     * 关键在于遍历顺序，前中后序应该选哪一种遍历顺序？ （一些同学这道题都过了，但是不知道自己用的是什么顺序）
     *
     * 遍历的过程中去翻转每一个节点的左右孩子就可以达到整体翻转的效果。
     *
     * 注意只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果
     *
     * 这道题目使用前序遍历和后序遍历都可以，唯独中序遍历不方便，因为中序遍历会把某些节点的左右孩子翻转了两次！建议拿纸画一画，就理解了
     *
     * 那么层序遍历可以不可以呢？依然可以的！只要把每一个节点的左右孩子翻转一下的遍历方式都是可以的！
     *
     * 递归法
     * 对于二叉树的递归法的前中后序遍历，已经在二叉树：前中后序递归遍历详细讲解了。
     *
     * 我们下文以前序遍历为例，通过动画来看一下翻转的过程:  （左右子树  交换位置）
     *
     *  我们来看一下递归三部曲：
     *
     * 1.确定递归函数的参数和返回值
     * 参数就是要传入节点的指针，不需要其他参数了，通常此时定下来主要参数，如果在写递归的逻辑中发现还需要其他参数的时候，随时补充。
     * 返回值的话其实也不需要，但是题目中给出的要返回root节点的指针，可以直接使用题目定义好的函数，所以就函数的返回类型为TreeNode*。
     *
     * TreeNode* invertTree(TreeNode* root)
     * 2.确定终止条件
     * 当前节点为空的时候，就返回
     *
     * if (root == NULL) return root;
     * 3.确定单层递归的逻辑
     * 因为是先前序遍历，所以先进行交换左右孩子节点，然后反转左子树，反转右子树。
     *
     * swap(root->left, root->right);
     * invertTree(root->left);
     * invertTree(root->right);
     *
     * 基于这递归三步法，代码基本写完，C++代码如下：
     *
     * class Solution {
     * public:
     *     TreeNode* invertTree(TreeNode* root) {
     *         if (root == NULL) return root;
     *         swap(root->left, root->right);  // 中
     *         invertTree(root->left);         // 左
     *         invertTree(root->right);        // 右
     *         return root;
     *     }
     * };
     */
    /**
     * DFS 递归算法   前后序遍历都可以
     * 中序不行，因为先左孩子交换孩子，再根交换孩子（做完后，右孩子已经变成了原来的左孩子），再右孩子交换孩子（此时其实是对原来的左孩子做交换）
     *
     * 总结
     * 针对二叉树的问题，解题之前一定要想清楚究竟是前中后序遍历，还是层序遍历。
     *
     * 二叉树解题的大忌就是自己稀里糊涂的过了（因为这道题相对简单），但是也不知道自己是怎么遍历的。
     *
     * 这也是造成了二叉树的题目“一看就会，一写就废”的原因。
     *
     * 针对翻转二叉树，我给出了一种递归，三种迭代（两种模拟深度优先遍历，一种层序遍历）的写法，都是之前我们讲过的写法，融汇贯通一下而已。
     *
     * 大家一定也有自己的解法，但一定要成方法论，这样才能通用，才能举一反三！
     */
    public TreeNode invertTree(TreeNode root){
        if (root == null){
            return root;
        }
        // 后序遍历
/*        invertTree(root.left);
        invertTree(root.right);
        swapChild(root);*/
        // 前序遍历
        swapChild(root);
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    // 广度优先搜索(BFS) 也就是层序遍历，层数遍历也是可以翻转这棵树的，因为层序遍历也可以把每个节点的左右孩子都翻转一遍，
    public TreeNode invertTree2(TreeNode root){
        Deque<TreeNode> deque = new LinkedList<>();
        if (root == null){
            return root;
        }
        deque.offer(root);

        while (!deque.isEmpty()){
            int len = deque.size();
            while (len > 0){
                TreeNode node = deque.poll();
                swapChild(node);
                if (node.left != null){
                    deque.offer(node.left);
                }
                if (node.right != null){
                    deque.offer(node.right);
                }
                len --;
            }
        }
        return root;
    }

    /**
     * 左右子数  反转
     * @param root
     */
    public void swapChild(TreeNode root){
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }

    public List<List<Integer>> getTreeNodeLevelOrder(TreeNode node){
        List<List<Integer>> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        // DFS
        //TreeNode root = invertTree(node);
        // BFS
        TreeNode root = invertTree2(node);

        if (root == null){
            return res;
        }
        deque.offerLast(root);

        while (!deque.isEmpty()){
            List<Integer> li = new ArrayList<>();
            int len = deque.size();

            for (int i = 0; i < len; i++) {

                TreeNode temp = deque.pollFirst();
                li.add(temp.val);
                if (temp.left != null){
                    deque.offerLast(temp.left);
                }
                if (temp.right != null){
                    deque.offerLast(temp.right);
                }
            }
            res.add(li);
        }
        return res;
    }

    public static void main(String[] args) {
        TreeNode leftNode1 = new TreeNode(1, null, null);
        TreeNode rightNode1 = new TreeNode(2, null, null);

        TreeNode leftNode2 = new TreeNode(6, null, null);
        TreeNode rightNode2 = new TreeNode(8, null, null);

        TreeNode leftNode = new TreeNode(4, leftNode1, rightNode1);
        TreeNode rightNode = new TreeNode(7, leftNode2, rightNode2);

        TreeNode root = new TreeNode(5, leftNode, rightNode);

        TreeNodeReserve treeNodeReserve = new TreeNodeReserve();

        System.out.println("反转后的二叉树，层序遍历结果： "+treeNodeReserve.getTreeNodeLevelOrder(root));

    }
}
